class Solution
{
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int len = 1;
        int begin = 0;
        for (int i = n - 1; i >= 0; --i) // i <= j
        {
            for (int j = n - 1; j >= i; --j)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                    // if(i == j  || i + 1 == j)
                    // {
                    //     dp[i][j] = true;
                    // }
                    // else if(i < j)
                    // {
                    //     dp[i][j] = dp[i+1][j-1];
                    // }
                }
                if (dp[i][j] == true && len < j - i + 1)
                {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, len);
    }
};
class Solution
{
public:
    bool checkPartitioning(string s)
    {
        int n = s.size();
        int count = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
        // 进行判断，如果[0,i-1),[i,j),[j+1,n-1)这三个范围里面有true，那么题目要求成立
        // i之前和j之后都要有1个数据，来构成3个范围
        // 【a,b,c】 : a为0，c为n-1，那么i取值0<i<n-1，j也是同理
        for (int i = 1; i < n - 1; i++)
        {
            for (int j = i; j < n - 1; ++j)
            {
                // 依次根据i和j的移动划分为3个范围
                // 如果i,j多次移动划分，划分的多个3个范围有一次是3个范围都是回文串，那么返回true
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
            }
        }
        return false;
    }
};

class Solution
{
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool>> is_dp(n, vector<bool>(n));
        // 快速确定某一个子串是不是回文串
        for (int i = n - 1; i >= 0; --i)
            for (int j = i; j < n; ++j)
                if (s[i] == s[j])
                    is_dp[i][j] = i + 1 < j ? is_dp[i + 1][j - 1] : true;
        // dp[i]表示：s[0，i]区间上的最长的子串，最少分割次数
        // j是字符串0到i区间中最后一次分割次数，j取值范围(0,i]
        // 如果j==0那么就表示0到i是一个回文串不用划分了
        // 如果j==i那么表示0到i的最后一次分割在i位置，前面0到i-1是回文串，加上i位置就不是了
        // 最后一次分割j到i如果是回文串，那么dp[i] = dp[j-1] + 1前面的加上我j这一刀就是最少分割次数
        // 如果j到i还不是回文串，那么j向后移动，直到j是0到i最后一次分割为止
        // 当j走到i位置时，产生了许多的结果，j在多个位置划分都将0到i变成了回文串，那么去最小值：min = min（min，dp[j-1]+1）
        vector<int> dp(n, INT_MAX);
        // 初始化为无穷大，防止干扰min函数的结果
        for (int i = 0; i < n; ++i)
        {
            if (is_dp[0][i]) // 如果0到i位置是回文串，那么就不用分割了，dp[i] = 0
                dp[i] = 0;
            else
            {
                for (int j = 1; j <= i; ++j) // j是最后一次分割的位置
                    if (is_dp[j][i] == true)
                        dp[i] = min(dp[i], dp[j - 1] + 1); // 选择j每个位置完成分割的最小值
            }
        }
        return dp[n - 1];
    }
};
class Solution
{
public:
    int longestPalindromeSubseq(string s)
    {
        // dp[i][j]表示：s字符串[i][j]区间内的所有的子序列，最长的回文子序列的长度
        // 因为是求子序列，当[i+1,j-1]如果是一个最长回文子序列，那么如果我s[i] == s[j]，此时[i,j]就是一个回文子序列

        // 如果我s[i] ！= s[j]，那么在我[i,j-1]和[i+1,j]里面查找回文子序列，然后取max就得到dp[i][j]

        // i<=j , dp[i][j]表示i到j范围内的最长回文子序列
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n)); // 不用初始化，需要越界的地方是[0,0]和[n-1,n-1]，但是i==j已经考虑到了
        // dp[i][j]可能从左边，下边，左下角得到 --- >>> dp[i+1][j-1],dp[i][j-1],dp[i+1][j]
        for (int i = n - 1; i >= 0; --i) // 填表方向从下往上，从左往右
        {
            for (int j = i; j < n; ++j)
            {
                if (s[i] == s[j]) // 左右两边
                {
                    if (i == j)
                        dp[i][j] = 1;
                    else if (i + 1 == j)
                        dp[i][j] = 2;
                    else if (i + 1 < j)
                        dp[i][j] = dp[i + 1][j - 1] + 2; //[i+1,j-1]回文子序列，s[i] == s[j]，[i,j]就是一个回文子序列
                }
                else
                {
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][n - 1]; // 起始位置为字符串开始0，终止位置为字符串结尾
    }
};

class Solution
{
public:
    int minInsertions(string s)
    {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; --i)
        {
            // 初始化数组为0
            // 将i+1==j这种情况放入到dp[i][j] = dp[i+1][j-1]中处理
            // 内层for循环从i+1开始，加上初始为0，那么i==j情况也不用考虑了
            for (int j = i + 1; j < n; ++j)
            {
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1];
                else
                    dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1;
            }
            // for(int j=i;j<n;++j)
            // {
            //     if(s[i] == s[j])
            //     {
            //         if(i == j)
            //             dp[i][j] = 0;
            //         else if(i+1==j)
            //             dp[i][j] = 0;
            //         else if(i+1 < j)
            //             dp[i][j] = dp[i+1][j-1];
            //     }
            //     else
            //     {
            //         dp[i][j] = min(dp[i][j-1],dp[i+1][j]) + 1;
            //     }
            // }
        }
        return dp[0][n - 1];
    }
};